后缀数组

Suffix Array

问题描述

首先来考虑一个字符串匹配的问题。

假设文本是一个长度为$n$的字符串$T$，模版是一个长度为$m$的字符串$P$，并且$m \leqslant n$。需要求出模版在文本中的所有匹配点$i$。如下图：

这个问题可以通过$KMP$算法解决。

但是如果匹配的模版有多个的时候，$KMP$算法不太合适，因为每次查找一个模版，都要遍历整个文本串。

或者说，更进一步的，如果我们都不能提前知道需要进行匹配的模版，需要我们对于一些动态的模版进行匹配，为了满足速度的要求，我们只能通过预处理$T$串，引入了后缀数组的概念。

算法介绍

问题建模

我们先来看$KMP$算法，$KMP$的重点和精华在于它的“失配函数”，是一种“用自己匹配自己”的思想。

根据$P$的结构，来进行失配函数的构造。我们可以大概的猜测到这个思想：如果一段字符串不能满足匹配的条件，那么即使我进行右移的操作，根据$P$的性质不同，即有可能还是无法满足匹配条件的。

失配函数的核心就在于找出：一旦出现了不匹配的情况，我们至少需要进行多少次的右移才有可能找到一个匹配情况。

如果寻找到了失配函数，那么剩下的问题也就可以迎刃而解。

对于后缀数组来说，问题要复杂的多，因为我们做不到对于模版的预处理，只能去处理文本串$T$。

根据刘汝佳书上的例子，对于一个给定的字符串，比如$BANANA$，我们可以在它的最后添加一个$\$$，某个从来没有出现的符号，使得后缀一定可以和一颗$Trie$的叶节点一一对应。注意这里的$\$$比所有的字符都小。

我们现在的任务就是将一个字符串的所有后缀按字典序进行一个排列。后缀就是从对应位置$i$开始到这个数组结束的全部字符组成的字符串。

大体的思想是首先对于字符串进行一次排序，如图：

之后每次都对于一个二元组进行排序，这里的每一个二元组都可以看作是后缀前两个字符的名次。如图：

之后依次类推，对后缀的前$2^k$的元素进行排序等等。

不过，分析可知，如果使用快速排序，这个算法的复杂度是$O(n\lg ^2n)$，仍然是比较高的。

所以这里我们使用了基数排序的方法，每次的复杂度为$O(n)$，最后的总的复杂度是$O(n\lg n)$。

求解方法

在前面我们已经详细讲解了算法的思想，具体实现上，不论是$KMP$还是后缀数组，都比较固定，基本没有太多的变化，可以套模版完成。

对于$KMP$算法，首先需要计算失配函数：

void getFail (char *P, int *f) {
	int m = strlen(P);
  	f[0] = 0;
  	f[1] = 0;
  	for (int i = 1; i < m; ++i) {
    	int j = f[i];
      	while (j && P[i] != P[j])
          	j = f[j];
      	f[i + 1] = P[i] == P[j] ? j + 1 : 0;
  	}
}

之后可以利用失配函数，计算最后的结果：

void find (char *T, char *P, int *f) {
  	int n = strlen(T), m = strlen(P);
  	getFail (P, f);
  	int j = 0;
  	for (int i = 0; i < n; ++i) {
    	while (j && P[j] != T[j]) j = f[j];
      	if (P[j] == T[j]) ++j;
      	if (j == m) print(i - m + 1);	// 找到匹配
  	}
}

对于后缀数组，其计算比较简单，但是使用起来比较灵活，这里给出一个比较标准的模版：

int wa[MAXN], wb[MAXN], wv[MAXN], ww[MAXN];
int sa[MAXN];
char str[MAXN];
inline bool cmp(int *r, int a, int b, int len) {
    return r[a] == r[b] && r[a + len] == r[b + len];  
}
void da(char *str, int n, int m) {  
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; ++i)
        ww[i] = 0;
    for(i = 0; i < n; ++i)
        ww[x[i] = str[i]]++;
    for(i = 1; i < m; ++i)
        ww[i] += ww[i-1];
    for(i = n - 1; i  >= 0; --i)
        sa[--ww[x[i]]] = i;
    for(j = p = 1; p < n; j <<= 1, m = p) {
        for(p = 0, i = n - j; i < n; ++i)
            y[p++]=i;
        for(i = 0; i < n; ++i)
            if(sa[i] >= j)
                y[p++] = sa[i] - j;
        for(i = 0; i < m; ++i)
            ww[i] = 0;
        for(i = 0; i < n; ++i)
            ww[wv[i] = x[y[i]]]++;
        for(i = 1; i < m; ++i)
            ww[i] += ww[i-1];
        for(i = n-1; i >= 0; --i)
            sa[--ww[wv[i]]] = y[i];
        for(t = x, x = y, y = t, x[sa[0]] = 0, p = i = 1; i < n; ++i)
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
    }
}

解题报告

Poj 2406 Power Strings

问题描述

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

• Input

  Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

• Output

  For each s you should print the largest n such that s = a^n for some string a.

算法设计

这道题目需要求出：如果字符串是某一个字串自我重复的结果，找出这个子串，如果有多个子串，选择最短的那一个。

显然，任何一个字符串都是它自己本身重复一次的结果。这里就需要使用自己本身去匹配自己，不难联想到$KMP$算法里面的失配函数，显然，如果满足右移以后可以匹配自己，那么这里一定存在子串并且满足：经过多次的重复以后，可以拼凑成原串。

所以，通过计算失配函数，其最后一项一定是满足性质的子串长。如果这个长度可以整除原串长，那么最后的结果就是题目所求的重复次数。

程序代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 1000000 + 5;
char str[MAXN];
int next[MAXN];
void getNext(size_t length) {
    int k = -1, j = 0;
    ::next[0] = -1;
    while (j < length) {
        if (k == -1 || str[k] == str[j]) {
            ++k;
            ++j;
            ::next[j] = k;
        }
        else {
            k = ::next[k];
        }
    }
}
int main () {
    std::ios::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    while (scanf("%s", str) && str[0] != '.') {
        size_t length = strlen(str);
        getNext(length + 1);
        if (!(length % (length - ::next[length]))) {
            printf("%lu\n", length / (length - ::next[length]));
        }
        else {
            printf("1\n");
        }
    }
}

性能分析

对于$KMP$算法的建表过程，是一个$O(n)$的算法，所以整个算法的复杂度其实就是$O(n)$。

编程技术技巧

这道题目在编程上没有太多的技巧可言，唯一需要注意的是：如何从求重复的子串联想到使用$KMP$算法的失配函数。对于算法还是需要灵活的理解。

Poj 3693 Maximum repetition substring

问题描述

The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of “ababab” is 3 and “ababa” is 1.

Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.

• Input

  The input consists of multiple test cases. Each test case contains exactly one line, which
  gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than 100,000.

  The last test case is followed by a line containing a ‘#’.

• Output

  For each test case, print a line containing the test case number( beginning with 1) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.

算法设计

这道题目是综合难度特别大的一题，设计的概念比较多，其中的$RMQ$算法，将会在下一章提及，这里先不做过多的说明。

首先，如果仅仅只求出了$sa$数组，其实是不够用的。通常情况下，我们需要定义两个辅助的数组：$rank$和$height$，其中，$rank_i$表示后缀$i$在$sa$数组中的下标。$heighti$表示定义为$sa{i - 1}$和$sa_i$的最长公共前缀$(LCP)$的长度。

如果两个字符串的$LCP$长度为$k$，意味着这两个字符串的前$k$个字符都相同，但是第$k +1$个字符不同。

对于两个后缀$j$和$k$，不妨设$rank_j < rank_i$，则可以证明后缀$i$和$k$的$LCP$长度为$height[rank_j+1], height[rank_j+2], \dots, height[rank_k]$中的最小值。即为$RMQ(height, rank_j+1, rank_k)$。

使用以上的方法进行构造以后，可以求解答案。

程序代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 100000 + 5;
int wa[MAXN], wb[MAXN], wv[MAXN], ww[MAXN];

int Rank[MAXN], sa[MAXN], lcp[MAXN], dp[MAXN][20], tmpRes[MAXN];

char str[MAXN];

inline bool cmp(int *r, int a, int b, int len) {
    return r[a] == r[b] && r[a + len] == r[b + len];  
}
void da(char *str, int n, int m) {  
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; ++i)
        ww[i] = 0;
    for(i = 0; i < n; ++i)
        ww[x[i] = str[i]]++;
    for(i = 1; i < m; ++i)
        ww[i] += ww[i-1];
    for(i = n - 1; i  >= 0; --i)
        sa[--ww[x[i]]] = i;
    for(j = p = 1; p < n; j <<= 1, m = p) {
        for(p = 0, i = n - j; i < n; ++i)
            y[p++]=i;
        for(i = 0; i < n; ++i)
            if(sa[i] >= j)
                y[p++] = sa[i] - j;
        for(i = 0; i < m; ++i)
            ww[i] = 0;
        for(i = 0; i < n; ++i)
            ww[wv[i] = x[y[i]]]++;
        for(i = 1; i < m; ++i)
            ww[i] += ww[i-1];
        for(i = n-1; i >= 0; --i)
            sa[--ww[wv[i]]] = y[i];
        for(t = x, x = y, y = t, x[sa[0]] = 0, p = i = 1; i < n; ++i)
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
    }
}
void getLcp(char *str, int n) {
    for (int i = 0; i <= n; ++i) {
        Rank[sa[i]] = i;
    }
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; ++i) {
        int j = sa[Rank[i] - 1];
        h ? h-- : 0;
        for (; j + h < n && i + h < n; ++h) {
            if (str[i + h] != str[j + h])
                break;
        }
        lcp[Rank[i] - 1] = h;
    }
}
void RMQ_init(int n) {
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = lcp[i - 1];
    }
    for (int i = 1; (1 << i) <= n; ++i) {
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
            dp[j][i] = min(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
        }
    }
}
int RMQ(int left, int right) {
    left = Rank[left];
    right = Rank[right];
    if (left > right)
        swap(left, right);
    ++left;
    int k = 0;
    while ((1 << (k + 1)) <= right - left + 1)
        ++k;
    return min(dp[left][k], dp[right - (1 << k) + 1][k]);
}
int main () {
    std::ios::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    int count = 0;
    while (scanf("%s", str) && str[0] != '#') {
        int length = (int)strlen(str);
        da(str, length + 1, 'z' + 1);
        getLcp(str, length);
        RMQ_init(length);
        int maxMatch = -1;
        int cnt = 0;
        for (int len = 1; len <= length; ++len) {
            int match;
            for (int i = 0; i + len < length; i += len) {
                match = RMQ(i, i + len);
                int pos = i - (len - match % len);
                match = match / len + 1;
                if (pos >= 0 && RMQ(pos, pos + len) >= len)
                    ++match;
                if (maxMatch < match) {
                    maxMatch = match;
                    cnt = 0;
                    tmpRes[cnt++] = len;
                }
                else if (maxMatch == match && len != tmpRes[cnt - 1])
                    tmpRes[cnt++] = len;
            }
        }
        bool flag = false;
        for (int i = 1; i <= length && !flag; ++i) {
            for (int j = 0; j < cnt && !flag; ++j) {
                if (RMQ(sa[i], sa[i] + tmpRes[j]) >= tmpRes[j] * (maxMatch - 1)) {
                    str[sa[i] + tmpRes[j] * maxMatch] = '\0';
                    flag = true;
                    printf("Case %d: %s\n", ++count, str + sa[i]);
                }
            }
        }
    }
}

性能分析

对于后缀数组而言，需要的构造时间是$O(n\lg n)$。而$RMQ$可以做到$O(n\lg n)$的建立时间，和$O(1)$的查询时间。所以总的时间为$O(n\lg n)$。

编程技术技巧

此题难度在于多种解题技巧的混合应用，单单就编程方面来说，技巧不是特别的多。

不过在最后进行输出的时候，可以直接利用printf的性质，将索引到的字符串尾部添加\0可以直接输出。